• Home
• Staff & Students
• Vacancies

 

Maria-Florina Balcan

 

Tuesday 28th July 2015

Time: 4.00pm

 

Ground Floor Seminar Room

25 Howland Street, London, W1T 4JG

Learning Submodular Functions

 

Submodular functions are discrete functions that model laws of
diminishing returns and enjoy numerous applications in many areas,
including algorithmic game theory, machine learning, and social networks.
For example, submodular functions are commonly used to model valuation
functions for bidders in auctions, and the influence of various subsets of
agents in social networks. Traditionally it is assumed that these
functions are known to the decision maker; however, for large scale
systems, it is often the case they must be learned from observations.

In this talk, I will discuss a recent line of work on studying the
learnability of submodular functions. I will describe general upper and
lower bounds on the learnability of such functions that yield novel
structural results about them of interest to many areas. I will also
discuss even better guarantees that can be achieved for important classes
that exhibit additional structure. These classes include functions with
bounded complexity used in modeling bidder valuation functions in
combinatorial auctions and probabilistic coverage functions that can be
used to model the influence function in classic models of information
diffusion in networks, as well as an application of our algorithms for
learning the influence functions in social networks.

 

Bio:

Maria-Florina Balcan is an Associate Professor in the School of
Computer Science at Carnegie Mellon University. Her main research
interests are machine learning, computational aspects in economics and
game theory, and algorithms. Her honors include the CMU SCS Distinguished
Dissertation Award, an NSF CAREER Award, a Microsoft Faculty Research
Fellowship, a Sloan Research Fellowship, and several paper awards. She was
a Program Committee Co-chair for COLT 2014 , and is currently a board
member of the International Machine Learning Society and a Program
Committee Co-chair for ICML 2016.